package 算法.分治法.快排;



import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {
    public static void main(String[] args) {
//        int [] a=new int[]{0,1,2,4,5,1,12,2,444,1321,12,1234134,143241,-1,7,7,7,7,7,-1,-100,3,3,3};
//        int [] a=new int[]{-1,-1,-1,-1,7,7,7,7,7,};
        int [] a=new int[]{5,4,3,2,6,2};
//        int [] a=new int[]{7,6,8,9};
//        int [] a=new int[]{7,6,9};
//        int [] a=new int[]{10,9};

//        System.out.println("请输入需要排序的数字个数:");
//        Scanner scanner = new Scanner(System.in);
//        int i = scanner.nextInt();
//        int[] a=new int[i];
//        System.out.println("请输入数字,不同数字请用空格隔开:");
//        for (int j = 0; j <i ; j++) {
//            a[j] = scanner.nextInt();
//        }

//        int [] a=new int[]{9,10};
        quickSort(a, 0, a.length-1);
//        quickSortRev(a,0 , a.length-1);
        System.out.println(Arrays.toString(a));
    }

    /**
     *  快排正序
     * @param nums
     * @param l 数组下界
     * @param h 数组上界
     */
    static void quickSort(int[] nums,int l,int h){
        if (nums==null){
            return;
        }
    int base=l;
    int i=base+1,j=h;
    if (l>=h){//l+1==h&&num[l]<=num[h]
        return;
    }
//    while (nums[base]<=nums[swap]){//基准点结束条件，即排序结束条件
//        quickSort(nums, i+1, h);
//    }
    while (i<=j){//搜索结束判定条件 i<=j保证了i的位置在基准点交换的前一个位置（10,9）***固定一***
            //和基准点进行判断 是否 向左或向右搜索
            if (nums[j]>=nums[base]&&nums[i]<=nums[j]){//num[j]必须大于等于num[base]，这样固定了i的位置（无论奇偶768 7689） ***固定二***
                j--;
            }
            if (nums[i]<nums[base]&&nums[i]<=nums[j]){//num[i+1]必须小于num[base]
                i++;
            }

            if (i<=j){
                if (nums[i]>nums[j]){//交换两个数的位置
                    int temp=nums[i];
                    nums[i]=nums[j];
                    nums[j]=temp;
                }
            }
        }
//        while (nums[base]<=nums[i]){//基准点结束条件，即当前部分排序结束条件
////            quickSort(nums, i+1, h);
//            return;
//        }
//int [] a=new int[]{0,1,2,4,5,1,12,2,444,1321,12,1234134,143241,-1,7,7,7,7,7};
        /**
         * 基准点交换
         * 因为没有设置哨兵i,j的先后顺序（其实应该让j先走的），导致哨兵的相遇位置出现
         * 了不确定性，误差在i、i-1之内，所以需要判断一下 例子7 6 9 和 7 6 8 9
         */
//        if (nums[i]<=nums[base]){
//            int temp2=nums[i];
//            nums[i]=nums[base];
//            nums[base]=temp2;
//            //向一直遍历左边的，在去遍历右边的，直到遍历整个数组
//            quickSort(nums,base , i-1);//左边
//            quickSort(nums, i+1, h);//右边
//        }else {
//            int temp2=nums[i-1];
//            nums[i-1]=nums[base];
//            nums[base]=temp2;
//            quickSort(nums,base , i-2);//左边
//            quickSort(nums, i, h);//右边
//        }
        //此时i只能在基准点的前一个位置 详见上面的***固定一、二***

             //仅在第一次才用到。。。
            int temp2 = nums[i - 1];
            nums[i - 1] = nums[base];
            nums[base] = temp2;

        quickSort(nums,base , i-2);//左边
        quickSort(nums, i, h);//右边

//        quickSort(nums, l, i-1);



//        if (base+1==i&&nums[base]<=nums[i]){
//            if ((i+1)<(nums.length-1)){
//                quickSort(nums, i+1, nums.length-1);//右边
//            }else{
//                return;
//            }
////{0,1,2,4,5,1,12,2,444,1321}
//        }
    }
    /**
     *  快排逆序
     * @param nums
     * @param l 数组下界
     * @param h 数组上界
     */
    static void quickSortRev(int[] nums,int l,int h){
        if (nums==null){
            return;
        }
        int base=l;
        int i=base+1,j=h;
        if (l>=h){//l+1==h&&num[l]<=num[h]
            return;
        }

        while (i<=j){//搜索结束判定条件 保证了i的位置（i-1必然可以和基准点交换）
            //和基准点进行判断 是否 向左或向右搜索
            if (nums[j]<=nums[base]&&nums[i]>=nums[j]){
                j--;
            }
            if (nums[i]>nums[base]&&nums[i]>=nums[j]){
                i++;
            }

            if (i<=j){
                if ((nums[i]<nums[j])){//交换两个数的位置
                    int temp=nums[i];
                    nums[i]=nums[j];
                    nums[j]=temp;
                }
            }
        }

        //此时i只能在基准点的前一个位置
        int temp2=nums[i-1];
        nums[i-1]=nums[base];
        nums[base]=temp2;
        quickSortRev(nums,base , i-1);//左边
        quickSortRev(nums, i+1, h);//右边

    }

}

